#ifndef HASH_MAP
#define HASH_MAP

#include "List/array_list.hpp"
#include <functional>
#include <memory>
#include <utility>
#define HIGH_RATIO 0.7
#define LOW_RATIO 0.1
#define MAX_SUCC 4
const int _prime_size= 28;
static const unsigned long _prime_list[_prime_size] =
{
53ul, 97ul, 193ul, 389ul, 769ul,
1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
1610612741ul, 3221225473ul, 4294967291ul
};

// 其实我试过用ArryList的，但是unique_ptr引入的可怕的模板元编程把我劝退了。。以后再研究
template <typename KeyType, typename ValueType, typename Hash=std::hash<KeyType>>
class HashMap {
public:
    HashMap();
    bool empty() const;
    size_t size() const;
    void put(const KeyType &key, const ValueType &value);
    bool has(const KeyType &key) const;
    ValueType& get(const KeyType &key);
    void remove(const KeyType &key);
    void print();
    std::vector<std::reference_wrapper<KeyType>> keys() const;
    std::vector<std::reference_wrapper<ValueType>> values() const;

private:
    void _fit();
    size_t _find_proper_cap();
    void _query(const KeyType &key, bool &is_find, bool &coner, size_t &pos) const;
    void _put(std::unique_ptr<std::pair<KeyType, ValueType>> && data);
    Hash _hash_fn;
    std::vector<std::unique_ptr<std::pair<KeyType, ValueType>>> _store;
    std::vector<std::unique_ptr<std::pair<KeyType, ValueType>>> _coner_case;
    size_t _size;
    size_t _cap_idx;
};


template <typename KeyType, typename ValueType, typename Hash>
HashMap<KeyType, ValueType, Hash>::HashMap(): _store(_prime_list[0]), _size(0), _cap_idx(0) { }

template <typename KeyType, typename ValueType, typename Hash>
bool HashMap<KeyType, ValueType, Hash>::empty() const {
    return _size == 0;
}

template <typename KeyType, typename ValueType, typename Hash>
size_t HashMap<KeyType, ValueType, Hash>::size() const {
    return _size;
}

template <typename KeyType, typename ValueType, typename Hash>
void HashMap<KeyType, ValueType, Hash>::put(const KeyType &key, const ValueType &value) {
    _size++;
    _put(std::make_unique<std::pair<KeyType, ValueType>>(key, value));
    _fit();
}

template <typename KeyType, typename ValueType, typename Hash>
bool HashMap<KeyType, ValueType, Hash>::has(const KeyType &key) const {
    bool is_find, coner;
    size_t pos;
    _query(key, is_find, coner, pos);
    return is_find;
}

template <typename KeyType, typename ValueType, typename Hash>
ValueType& HashMap<KeyType, ValueType, Hash>::get(const KeyType &key) {
    bool is_find, coner;
    size_t pos;
    _query(key, is_find, coner, pos);
    if(is_find) {
        if(coner)
            return _coner_case[pos]->second;
        else
            return _store[pos]->second;
    } else throw "Can't find key in HashMap!";
}

template <typename KeyType, typename ValueType, typename Hash>
void HashMap<KeyType, ValueType, Hash>::remove(const KeyType &key) {
    bool is_find, coner;
    size_t pos;
    _query(key, is_find, coner, pos);
    if(is_find) {
        _size--;
        if(coner)
            _coner_case.erase(_coner_case.begin() + pos);
        else
            _store[pos].reset(nullptr);
    }
    _fit();
}

template <typename KeyType, typename ValueType, typename Hash>
void HashMap<KeyType, ValueType, Hash>::print() {
    std::cout << "{";
    auto mkeys = keys();
    for(auto it = mkeys.begin() ; it != mkeys.end() ; it++) {
        KeyType &key = *it;
        std::cout << key << ':' << get(key);
        if(it != mkeys.end() - 1) std::cout << ", ";
    }
    std::cout << "}" << std::endl;
}

template <typename KeyType, typename ValueType, typename Hash>
std::vector<std::reference_wrapper<KeyType>> HashMap<KeyType, ValueType, Hash>::keys() const {
    std::vector<std::reference_wrapper<KeyType>> key_refs;
    for(auto &store: _store) {
        if(store) key_refs.push_back(std::ref(store->first));
    }
    for(auto &store: _coner_case) {
        key_refs.push_back(std::ref(store->first));
    }
    return key_refs;
}

template <typename KeyType, typename ValueType, typename Hash>
std::vector<std::reference_wrapper<ValueType>> HashMap<KeyType, ValueType, Hash>::values() const {
    std::vector<KeyType&> value_refs;
    for(KeyType key_ptr: keys()) {
        value_refs.push_back(get(*key_ptr));
    }
    return value_refs;
}

template <typename KeyType, typename ValueType, typename Hash>
void HashMap<KeyType, ValueType, Hash>::_fit() {
    size_t capacity = _store.size();
    if((size() > capacity * HIGH_RATIO && _cap_idx != _prime_size - 1) || (size() < capacity * LOW_RATIO && _cap_idx != 0)) {
        size_t new_cap = _find_proper_cap();
        std::vector<std::unique_ptr<std::pair<KeyType, ValueType>>> temp_store;
        for(KeyType &key: keys()) {
            bool is_find, coner;
            size_t pos;
            _query(key, is_find, coner, pos);
            if(coner)
                temp_store.push_back(std::move(_coner_case[pos]));
            else
                temp_store.push_back(std::move(_store[pos]));
        }
        _store.clear();
        _store.resize(new_cap);
        _coner_case.clear();
        for(auto &data: temp_store) {
            _put(std::move(data));
        }
    } else return;
}

template <typename KeyType, typename ValueType, typename Hash>
size_t HashMap<KeyType, ValueType, Hash>::_find_proper_cap() {
    size_t capacity = _store.size();
    if(size() > capacity * HIGH_RATIO && _cap_idx != _prime_size - 1) {
        return _prime_list[++_cap_idx];
    } else if(size() < capacity * LOW_RATIO && _cap_idx != 0) {
        return _prime_list[--_cap_idx];
    }
    return _prime_list[_cap_idx];

}

template <typename KeyType, typename ValueType, typename Hash>
void HashMap<KeyType, ValueType, Hash>::_query(const KeyType &key, bool &is_find, bool &coner, size_t &pos) const{
    pos = _hash_fn(key) % _store.size();
    int cnt = 0;
    bool out_of_succ = false;
    while(_store[pos] && _store[pos]->first != key) {
        pos = (pos + 1) % _store.size();
        if(cnt == MAX_SUCC) {
            out_of_succ = true;
            break;
        } else
            cnt++;
    }
    if(out_of_succ) {
        for(size_t i = 0 ; i < _coner_case.size() ; ++i) {
            if(_coner_case[i]->first == key) {
                is_find = true;
                coner = true;
                pos = i;
                return;
            }
        }
        is_find = false;
        return;
    } else {
        if(_store[pos]) {
            is_find = true;
            coner = false;
        } else {
            is_find = false;
        }
    }
}

template <typename KeyType, typename ValueType, typename Hash>
void HashMap<KeyType, ValueType, Hash>::_put(std::unique_ptr<std::pair<KeyType, ValueType>> && data) {
    size_t pos = _hash_fn(data->first) % _store.size();
    int cnt = 0;
    bool out_of_succ = false;
    while(_store[pos]) {
        pos = (pos + 1) % _store.size();
        if(cnt == MAX_SUCC) {
            out_of_succ = true;
            break;
        } else
            cnt++;
    }
    if(out_of_succ)
        _coner_case.push_back(std::move(data));
    else
        _store[pos] = std::move(data);
    _fit();
}

#endif